package com.utils.bfs;

import java.util.*;


public class Graph {
    private List<Vertex> vertexList = new ArrayList<>();             // 节点集合
    private Map<String, List<String>> adjMat = new HashMap<>();      // 边关系集合
    private Stack<Vertex> theStack = new Stack<>();

    public void addVertex(String lab) {
        vertexList.add(new Vertex(lab));
    }

    /**
     * 边连接
     */
    public void addEdge(String startNode, String endNode) {
        List<String> nextNodeList = adjMat.computeIfAbsent(startNode, k -> new ArrayList<>());
        for (String oneNextNodeLabel : nextNodeList) {
            if (oneNextNodeLabel.equals(endNode)) {
                return;
            }
        }
        nextNodeList.add(endNode);
    }

    /**
     * 如果一条路径，在旧有的所有路径中都不存在，则代表是一条新路径，可以继续遍历：
     * 不依靠节点的是否已访问标志来识别当前路径是否可选，
     * 在遍历路径中带环的图有效果
     */
    private boolean existPath(String nextEnd, List<String> curPath, List<List<String>> allPath) {
        String head = curPath.get(0);
        List<String> tmpPath = new ArrayList<>(curPath);

        if (nextEnd != null && !nextEnd.equals("")) {
            tmpPath.add(nextEnd);
        }

        for (List<String> onePath : allPath) {
            if (!onePath.get(0).equals(head)) {
                continue;
            }

            if (tmpPath.size() > onePath.size()) {
                continue;
            }

            int sameCount = 0;
            for (int i = 0; i < tmpPath.size(); i++) {
                if (tmpPath.get(i).equals(onePath.get(i))) {
                    sameCount++;
                }
            }

            if (sameCount == tmpPath.size()) {
                return true;
            }
        }

        return false;
    }

    /**
     * 深度优先遍历
     * 目前只选中一个节点作为开始节点来遍历出所有路径，
     * 如果希望遍历所有路径，可以在本方法外部增加一个for循环
     */
    public List<List<String>> mst() {
        Vertex firstVertex = vertexList.get(0);
        theStack.push(firstVertex);

        List<List<String>> allPathList = new ArrayList<>();
        List<String> onePath = new ArrayList<>();
        onePath.add(firstVertex.label);
        allPathList.add(onePath);

        while (!theStack.isEmpty()) {
            Vertex currentVertex = theStack.peek();
            String currentVertexLabel = currentVertex.label;
            // 如果在for循环中没有找到后续的节点，也要后退一个节点
            Vertex nextNode = null;

            boolean cycleEnd = false;
            boolean existPath = false;

            List<String> nextNodeList = adjMat.get(currentVertexLabel);
            if (nextNodeList != null && !nextNodeList.isEmpty()) {
                for (String oneNextNodeLabel : nextNodeList) {
                    existPath = false;

                    if (existPath(oneNextNodeLabel, onePath, allPathList)) {
                        // 如果历史路径集合中已经包含了该边，则继续后退一个节点
                        existPath = true;
                    } else {
                        if (onePath.indexOf(oneNextNodeLabel) >= 0) {
                            // 虽然是一条全新的边，但是新边的结束节点已经在路径中存在了，则也要结束当前的探测路径
                            onePath.add(oneNextNodeLabel);
                            cycleEnd = true;
                            break;
                        }

                        nextNode = getVertexByFlag(oneNextNodeLabel);
                        break;
                    }
                }
            }

            if (nextNode == null) {
                // 如果该节点已经是路径上的最后一个节点了，则弹出该节点，尝试在前一个节点基础上找其他分支路径
                if (existPath || !cycleEnd) {
                    // 因为没有将末端节点 push 进来，所以无需pop
                    theStack.pop();
                }

                if (existPath) {
                    // 当所有的路径都走完之后，最原始的节点会被删掉，这导致最后一条路径是个空的List
                    onePath.remove(onePath.size() - 1);
                } else {
                    // 新建一条路径
                    List<String> newPath = new ArrayList<>(onePath);
                    newPath.remove(newPath.size() - 1);
                    onePath = newPath;
                    allPathList.add(onePath);
                }
            } else {
                theStack.push(nextNode);
                onePath.add(nextNode.label);
            }
        }

        // 当所有的路径都走完之后，最原始的节点会被删掉，这导致最后一条路径是个空的List
        int delPathIdx = 0;
        for (int i = 0; i < allPathList.size(); i++) {
            if (allPathList.get(i).isEmpty()) {
                delPathIdx = i;
            }
        }
        allPathList.remove(delPathIdx);
        //System.out.println(allPathList);

        return allPathList;
    }

    /**
     * 找到一个未访问的节点下标，如果都访问完毕了，则返回-1
     *
     */
    private Vertex getVertexByFlag(String nodeLabel) {
        for (Vertex oneVertex : vertexList) {
            if (oneVertex.label.equals(nodeLabel)) {
                return oneVertex;
            }
        }
        return null;
    }


}
